package com.gao.alg.geek;

import java.util.HashMap;
import java.util.Map;

public class ClimbStairs2 {


    public int climbStairs(int n) {
        if(n <= 2){
            return n;
        }
        int count = climbStairs(n-1) + climbStairs(n-2);
        return count;
    }


    private Map<Integer,Integer> cache = new HashMap<>();
    public int climbStairsWithCache(int n) {
        if (n <= 2){
            return n;
        }
        if (cache.containsKey(n)){
            return cache.get(n);
        }
        int count = climbStairs(n-1) + climbStairs(n-2);
        cache.put(n,count);
        return count;
    }


    /**
     * 递归转迭代循环
     */
    public int climbStairsByIterator(int n) {
        if (n <= 2){
            return n;
        }
        int ret = 0;
        int pre = 2;
        int prePre = 1;
        for (int i = 3; i <= n; i++) {
            ret = pre + prePre;
            prePre = pre;
            pre = ret;
        }
        return ret;
    }
}
